/*
 * Heap.h
 *
 *  Created on: Sep 16, 2012
 *      Author: romina
 */

#ifndef HEAP_H_
#define HEAP_H_

#include <iostream>
#include <string>
#include <exception>
#include "Buffer.h"

using namespace std;

namespace ordenamiento {

class Heap {
private:
	Buffer* heap;				//vector de palabras a ordenar
	int tamanio;    			//maximo tamanio del heap
	int last;					//ultima posicion accesible
	//true si es hoja
	bool isLeaf(int posicion);
	//retorna la posicion del padre
	int parent(int pos);
	//retorna la posicion del hijo izquierdo
	int leftH(int pos);
	//retorna la posicion del hijo derecho
	int rightH(int pos);
public:
	Heap(Buffer* buffer);
	//achica el heap decrementando la ultima posicion
	void decreaseLast();
	//intercambia el valor de la raiz con la de la ultima posicion
	void swapRaizLast();
	//ubica la posicion al final del heap
	void restaurarLast();
	//devuelve la raiz del heap
	string getRaiz();
	//retorna el valor de una posicion
	string getValue(int pos);
	//inserta en una posicion
	void setValue(int pos, string value);
	//retorna ultima posicion
	int getLast();
	//setea ultima posicion
	void setLast(int last);
	//capacidad del heap
	int getSize();
	//reordena el heap
	void siftdown(int pos);
	//primer_ordenamiento
	void buildheap();
	//intercambia los datos de dos posiciones
	void swap(int pos1, int pos2);
	//Shift a izquierda de los elementos del array que representa el heap
	//El elemento de la posicion position queda como cima del heap
	void shiftLeft(int position);
	//destructor
	virtual ~Heap();
};

} /* namespace ordenamiento */
#endif /* HEAP_H_ */
